package com.zm.demo.core.leetcode;

import static java.lang.System.out;

/**
 * 丑数 II
 * 编写一个程序，找出第 n 个丑数。

 丑数就是只包含质因数 2, 3, 5 的正整数。
 * @author zoum
 * @create 2020/1/10 17:27
 */
public class NthUglyNumber {

    public int nthUglyNumber(int n) {
        if (n == 1){
            return 1;
        }

        int base1 = 1;
        int base2 = 1;
        int base3 = 1;

        int num=0;

        while (n>0){
            if (2*base1 <= 3*base2 && 2*base1 <= 5*base3 ){
                if (num >= 2*base1){
                    base1++;
                }else {
                    n--;
                    num = 2*base1;
                    base1++;
                }
            }else if (3*base2 <= 2*base1 && 3*base2 <= 5*base3 ){
                if (num >= 3*base2){
                    base2++;
                }else {
                    n--;
                    num = 3*base2;
                    base2++;
                }
            }else if (5*base3 <= 2*base1 && 5*base3 <= 3*base2 ){
                if (num >= 5*base3){
                    base3++;
                }else {
                    n--;
                    num = 5*base3;
                    base3++;
                }
            }

        }
        return num;
    }

    public static void main(String[]args) {
        out.println(new NthUglyNumber().nthUglyNumber(100));
    }

}
